import java.util.ArrayList;
import java.util.List;

/**
 * 60. 排列序列
 * https://leetcode-cn.com/problems/permutation-sequence/
 */
public class Solutions_60 {
    public static void main(String[] args) {
//        int n = 3, k = 3;  // output: 213

//        int n = 4, k = 9;  // output: 2314

        for (int i = 1; i <= 2; i++) {
//            String result = getPermutation(n, k);
            String result = getPermutation(2, i);
            System.out.println(result);
        }
    }

    /**
     * [0,5)   [6,12)  [13, 18)  [19, 24)
     * 1234    2134     3124     4123
     * 1243    2143     3142     4132
     * 1324    2314     3214     4213
     * 1342    2341     3241     4231
     * 1423    2413     3412     4312
     * 1432    2431     3421     4321
     *
     * n = 1，那么最多有 1 位，共有 1 种组合
     * n = 2，那么最多有 2 位，共有 1 * 2 = 2 种组合
     * n = 3，那么最多有 3 位，共有 1 * 2 * 3 = 6 种组合
     * n = 4，那么最多有 4 位，共有 1 * 2 * 3 * 4 = 24 种组合
     *
     * n = 4, k = 9 为例，第 9 个排列为：2314
     * 推算过程：
     * 首先将 k - 1 = 8，因为在计算中，第 0 位才是表示 1234
     * 此时列表中有：1 2 3 4
     * 1. 确定第 1 位：8 / 6 = 1，列表中索引 1 上的数字为 2
     *    为什么除 6？因为以 1, 2, 3, 4 开头的，每种都有 6 种情况，即 1 * 2 * 3
     *    确定第 1 位后，k % 6 = 2（直接取余可能报错，余数为 0 时报错）
     *    则更换取余方式：k - (1 * 6) = 2
     *    移除数字 2 后，列表中有：1 3 4
     * 2. 确定第 2 位：2 / 2 = 1，列表中索引 1 上的数字为 3
     *    为什么除 2？因为以 21，23，24 开头的，每种都有 2 种情况，即 1 * 2
     *    则更换取余方式：k - (1 * 2) = 0
     *    移除数字 3 后，列表中有：1 4
     */
    public static String getPermutation(int n, int k) {
        if (n == 1) {
            return "1";
        }
        StringBuilder sb = new StringBuilder();
        List<Integer> list = new ArrayList<>();
        // 将 [1, n] 区间的数字，添加到列表中，后续将通过计算得到的索引来获取数字
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }

        // 提前计算好计算阶乘（需要用阶乘进行计算，而不是使用阶梯公式，注意注意）
        // arr[4] = 24，表示 4! 结果是 24
        int[] arr = new int[n + 1];
        arr[0] = arr[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] * i;
        }

        // 计算前，先将 k - 1，因为 k = 1 时，表示取第 1 个排列，而在程序中，k = 0 才是第 1 个排列
        k -= 1;
        for (int i = 1; i <= n; i++) {
            int loc = k / arr[n - i];
            sb.append(list.get(loc));
            // 直接用 k % loc，会报错，因为 loc 可能为 0
            k = k - loc * arr[n - i];
            // 数字添加后，在列表中移除数字
            list.remove(loc);
            if (k == 0) {
                // 剪枝：不需要计算了，后续取数字都是从索引 0 上取
                break;
            }
        }
        for (int num : list) {
            sb.append(num);
        }
        return sb.toString();
    }
}
